package sort;

/**
 * 堆排序
 */
public class HeapSort {

    public void sort(int[] nums) {
        initHeap(nums);
        for (int i = nums.length - 1; i > 0; i--) {
            swap(nums, 0, i);
            buildHeap(nums, 0, i);
        }
    }

    public void initHeap(int[] nums) {
        for (int i = nums.length / 2; i >= 0; i--) {
            buildHeap(nums, i, nums.length);
        }
    }

    public void buildHeap(int[] nums, int p, int heapSize) {
        if (p >= heapSize) return;

        int left = 2 * p + 1;
        int right = 2 * p + 2;

        int target = p;
        if (left < heapSize && nums[left] > nums[target]) {
            target = left;
        }
        if (right < heapSize && nums[right] > nums[target]) {
            target = right;
        }

        if (target != p) {
            swap(nums, p, target);
            buildHeap(nums, target, heapSize);
        }
    }

    public void swap(int[] nums, int p1, int p2) {
        int temp = nums[p1];
        nums[p1] = nums[p2];
        nums[p2] = temp;
    }

    public static void main(String[] args) {
//        int[] nums = {2,3,1,9,6,4,6};
        int[] nums = GenNums.rank(10000);
        HeapSort heapSort = new HeapSort();
        heapSort.sort(nums);
        GenNums.printNums(nums);
        System.out.println(GenNums.check(nums));
    }

}
